package com.example.demo.class14_tanxin;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @program: java_base
 * @description: 并查集 对象方式实现
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/28 09:43
 */
public class Code05_UnionFindDemo {


    public static class Node<V> {
        V value;
        public Node(V value) {
            this.value = value;
        }
    }

    /**
     * isSameSet(E e1, E e2)  两个元素是否在同一个 集合内？
     * union(a,e)  合并两个集合的全体，合并的集合是a全体元素+e全体元素
     */


    class UnionFind<V> {
        HashMap<V, Node<V>> nodes;
        HashMap<Node<V>, Node<V>> parents;
        HashMap<Node<V>, Integer> sizeMap;

        public UnionFind(List<V> list) {
            nodes = new HashMap<>();
            parents = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V v:list) {
                Node node = new Node(v);
                nodes.put(v, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        public boolean isSameSet(V v1, V v2) {
            Node<V> vNode1 = nodes.get(v1);
            Node<V> vNode2 = nodes.get(v2);

            Node<V> father = findFather(vNode1);
            Node<V> father1 = findFather(vNode2);
            return father == father1;
        }


        public void union(V v1, V v2) {
            if (!isSameSet(v1, v2)) {
                Node<V> vNode1 = new Node<>(v1);
                Node<V> head1 = getHead(vNode1);
                Node<V> vNode2 = new Node<>(v2);
                Node<V> head2 = getHead(vNode2);

                Integer integer1 = sizeMap.get(head1);
                Integer integer2 = sizeMap.get(head2);

                if (integer1 >= integer2) {
                    parents.put(head2, head1);
                    sizeMap.put(head1, integer2 + integer1);
                    sizeMap.remove(head2);
                } else {
                    parents.put(head1, head2);
                    sizeMap.put(head2, integer2 + integer1);
                    sizeMap.remove(head1);
                }
            }
        }

        // // 给你一个节点，请你往上到不能再往上，把代表返回
        private Node<V> getHead(Node<V> vNode) {
            while (vNode != parents.get(vNode)) {
                vNode = parents.get(vNode);
            }
            // 替换的时候，中间节点没有替换 parent
            return vNode;
        }

        private Node<V> findFather(Node<V> cur) {
            Stack<Node<V>> path = new Stack<>();
            while (cur != parents.get(cur)) {
                path.push(cur);
                cur = parents.get(cur);
            }
            while (!path.isEmpty()){
                parents.put(path.pop(), cur);
            }
            return cur;
        }
    }
}
